package leetcode.题库.结构设计;

import java.util.HashMap;

/**
 * description: LRU
 *
 * @author 颜真明
 * @date 2024/3/13  14:32
 */
public class LruCache146 {

    // 1、内部属性 容量、目前长度、双向链表、HashMap、前节点、后节点
    int size;
    int capacity;
    DoubleLinkedNode headNode;
    DoubleLinkedNode tailNode;
    HashMap<Integer, DoubleLinkedNode> hashMap;

    class DoubleLinkedNode{
        int key;
        int value;
        DoubleLinkedNode pre;
        DoubleLinkedNode next;
        DoubleLinkedNode(){}
        DoubleLinkedNode(int key, int value){
            this.key = key;
            this.value = value;
        }
    }

    // 2、构造方法
    LruCache146(int capacity){
        this.capacity = capacity;
        size = 0;
        hashMap = new HashMap<>();
        headNode = new DoubleLinkedNode();
        tailNode = new DoubleLinkedNode();
        headNode.next = tailNode;
        tailNode.pre = headNode;
    }

    // 3、get方法
    int get(int key) {
        DoubleLinkedNode node = hashMap.get(key);
        if(node != null) {
            moveToHead(node);
            return node.value;
        }
        return -1;
    }
    // 4、put方法
    void put(int key, int value) {
        DoubleLinkedNode node = new DoubleLinkedNode(key, value);
        DoubleLinkedNode val = hashMap.get(key);
        hashMap.put(key, node);
        if (val != null) {
            deleteNode(val);
            insertToHead(node);
        } else {
            size++;
            insertToHead(node);
            if (size > capacity) {
                DoubleLinkedNode tail = deleteTail();
                hashMap.remove(tail.key);
                size--;
            }
        }

    }

    // 5、删除节点
    void deleteNode(DoubleLinkedNode node){
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }
    // 6、插入到头部
    void insertToHead(DoubleLinkedNode node){
        node.pre = headNode;
        node.next = headNode.pre;
        headNode.pre.pre = node;
        headNode.next = node;
    }
    // 7、移动到头部 5+6
    void moveToHead(DoubleLinkedNode node){
        deleteNode(node);
        insertToHead(node);
    }
    // 8、删除尾节点
    DoubleLinkedNode deleteTail(){
        DoubleLinkedNode tmpNode = tailNode.pre;
        tailNode.pre = tmpNode.pre;
        tmpNode.pre.next = tailNode;
        return tmpNode;
    }
}
